package Leetcode.LC034;

/***
 * 有序数组，二分查找
 */
public class Sloution {
    /***
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left=findleft(nums,target);
        int right=findright(nums,target);
        //判断非法状态
        if(left==-3 || right==-3) return new int[]{-1,-1};
        if(right-left>1) return new int[]{left+1,right-1};
        return new int[]{-1,-1};
    }

    /***
     * 找右边界，二分查找右边界就是下一个的最左起始边
     * @param nums
     * @param target
     * @return
     */
    private int findright(int[] nums, int target) {
        int rightborad=-3;
        int left=0,right=nums.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
                rightborad=left;
            }
        }
        return rightborad ;
    }

    /***
     * 找左边界，与上述类似
     * @param nums
     * @param target
     * @return
     */
    private int findleft(int[] nums, int target) {
        int leftboder=-3;
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
                leftboder=right;
            }
        }
        return leftboder;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[] ints = {1,1,2,3,5,6};
        int target=1;
        int[] res = sloution.searchRange(ints,target);
        for(int i:res){
            System.out.print(i);
        }
    }
}
